package com.leetcode.algorithm.y22.m05;

/**
 * 509. 斐波那契数 
 * https://leetcode.cn/problems/fibonacci-number/
 * 
 * @author jie.deng
 *
 */
class Question0509Solution02 {

	// 利用DP思想，加上空间优化
	public int fib(int n) {
		if (n <= 1) {
			return n;
		}

		// 初始状态
		int i0 = 0;
		int i1 = 1;

		for (int i = 2; i <= n; i++) {
			// 状态转移方程
			int tmp = i1 + i0;
			i0 = i1;
			i1 = tmp;
		}

		return i1;
	}

}